package com.woniu.filter;

import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;

/**
 * 算法过程：
 * 1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数
 * 2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
 * 3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
 * 4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。
 */
public class BloomFilterHelper<T> {
    private Long bitSize; // 二进制数组大小
    private int numHashFunctions; // hash函数个数
    private Funnel<T> funnel;
    /**
     * @param expectedInsertions 预估插入数据数量
     * @param fpp                允许数据误差率
     * @param funnel
     */
    public BloomFilterHelper(Long expectedInsertions, double fpp, Funnel<T> funnel) {
        this.funnel = funnel;
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
    }
    /**
     * 计算bit数组大小
     * @param n 预估插入数据数量
     * @param p 允许数据误差率
     * @return
     */
    private long optimalNumOfBits(long n, double p) {
        if (p == 0) p = Double.MIN_VALUE;
        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }
    /**
     * 计算hash函数个数
     * @param n 预估插入数据数量
     * @param m bit数组大小
     * @return
     */
    private int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }
    /**
     * 计算元素的hash散列下标
     * @param value 元素
     * @return
     */
    public Long[] mightContain(T value) {
        Long[] longs = new Long[numHashFunctions];
        long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
        int hash1 = (int) hash64;
        int hash2 = (int) (hash64 >>> 32);
        for (int i = 1; i <= numHashFunctions; ++i) {
            int combinedHash = hash1 + i * hash2;
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            longs[i - 1] = combinedHash % bitSize;
        }
        return longs;
    }
}
